#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import Counter


class Solution:
    """
    @param source : A string
    @param target: A string
    @return: A string denote the minimum window, return "" if there is no such a string
    """
    def minWindow(self, source , target):
        self.source = source
        self.match_count = 0
        self.target_counter = Counter()

        self.target_len = len(target)
        self.source_len = len(source)

        self.min_length = self.source_len + 1
        self.count = 0
        self.left = 0
        self.right = 0
        self.result = ''

        for t in target:
            self.target_counter[t] += 1
        # print(self.target_counter)

        for self.right, c in enumerate(source):
            # extend window(extend right)
            self.target_counter[c] -= 1
            if self.target_counter[c] >= 0:
                self.count += 1

            if self.is_count_match:
                while self.is_count_match:
                    # 移动左边直到不能满足 count匹配
                    # self.refresh_minimum_old()
                    print(self.left)
                    self.move_left()        # 尽量左移, 剔除不相干元素, 还有多出来的在target中的元素

                # 这时候left如果左移一位, 是滑动窗口中刚好可以contain target的"局部最短字符串".
                self.try_update_global_min()

        # print('left [%s]' % self.left)
        # print('right [%s]' % self.right)
        return self.result

    def move_left(self):
        '''
            move_left 不会超过还未处理过的字符.
            因为在count匹配的情况下才进行move_left, 如果left 超过right, count一定不匹配.
            assert source[left:right+1] contains target
        '''
        assert self.left <= self.right
        c = self.source[self.left]

        self.target_counter[c] += 1
        if self.target_counter[c] > 0:
            self.count -= 1
            # match target char

        self.left += 1

    def try_update_global_min(self):
        local_min = self.right - (self.left - 1) + 1
        print('local_min %s' % local_min)
        if local_min < self.min_length:
            # print('local_min is [%s]' % local_min)
            self.min_length = local_min
            self.result = self.source[self.left-1:self.right+1]

    def refresh_minimum_old(self):
        local_min = self.right - self.left + 1
        if local_min < self.min_length:
            # print('local_min is [%s]' % local_min)
            self.min_length = local_min
            self.result = self.source[self.left:self.right+1]

    @property
    def is_count_match(self):
        # 此时self.target_counter 都为0(或者小于0): 不存在与target中, 但是在source中出现的一定为负数
        return self.count == self.target_len


def test():
    s = Solution()
    # r = s.minWindow('abc', 'bc')
    # r = s.minWindow('sasdfegab', 'fda')
    r = s.minWindow('abc', 'ac')
    print(r)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
